package DoExercise.HSP_ZCY.A014_贪心_总是当前的全局最优解;

import java.util.Comparator;
import java.util.PriorityQueue;


/**
 * 输入: 正数数组costs、正数数组profits、正数K、正数M
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * K表示你只能串行的最多做k个项目
 * W表示你初始的资金
 * <p>
 * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
 * 输出：你最后获得的最大钱数。
 * <p>
 *
 *
 */
public class Code05_如何挣到最多的资金
{
    
    public static void main(String[] args)
    {
        int[] Profits = {100,200};
        int[] Cost = {10,20};
        System.out.println(findMaximizedCapital(10, 10, Profits, Cost));
    }
    
    /**
     *
     * 贪心策略:每次都选择花费最小的项目中收益最高的做
     *
     * @param K       串行的最多做k个项目
     * @param W       初始的资金
     * @param Profits 表示i号项目在扣除花费之后还能挣到的钱(利润)
     * @param Cost 表示i号项目的花费
     * @return
     */
    public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Cost)
    {
        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        for (int i = 0; i < Profits.length; i++)
        {
            minCostQ.add(new Program(Profits[i], Cost[i]));
        }
        for (int i = 0; i < K; i++)
        {
            while (!minCostQ.isEmpty() && minCostQ.peek().cost <= W)
            {
                maxProfitQ.add(minCostQ.poll());
            }
            
            //项目花费太高或者项目已经做完，无项目可做，返回当前 W
            if (maxProfitQ.isEmpty())
            {
                return W;
            }
            
            W += maxProfitQ.poll().profit;//当前能做的利润最多的项目
        }
        return W;
    }
    
    public static class Program
    {
        public int profit;
        public int cost;
        
        public Program(int p, int c)
        {
            this.profit = p;
            this.cost = c;
        }
    }
    
    //花费的小根堆
    public static class MinCostComparator implements Comparator<Program>
    {
        @Override
        public int compare(Program o1, Program o2)
        {
            return o1.cost - o2.cost;
        }
    }
    
    //利润的大根堆
    public static class MaxProfitComparator implements Comparator<Program>
    {
        @Override
        public int compare(Program o1, Program o2)
        {
            return o2.profit - o1.profit;
        }
    }
    
}
